# 

# 

# ### 90. Maximum Flow 问题解释

# 

# **问题概述**：

# 

# 最大流问题（Maximum Flow Problem）是图论和网络流理论中的一个经典问题。给定一个有向图，图中的边有容量限制（即单位时间内最多可以通过的流量），源点（source）和汇点（sink）各一个，我们需要找到一种流量分配方案，使得从源点到汇点的流量总和最大，同时满足每条边的流量不超过其容量限制，且流入每个节点的流量等于流出该节点的流量（除了源点和汇点）。

# 

# **问题建模**：

# 

# - **图**：通常使用有向图来表示网络，图中的节点表示网络中的设备或地点，边表示设备或地点之间的连接。

# - **容量**：每条边都有一个容量限制，表示该边在单位时间内可以传输的最大流量。

# - **源点和汇点**：源点是流量的起点，汇点是流量的终点。

# - **流量守恒**：除了源点和汇点外，流入节点的流量必须等于流出该节点的流量。

# 

# **解决方法**：

# 

# 最大流问题通常使用Ford-Fulkerson算法或其改进算法（如Edmonds-Karp算法、Dinic算法等）来解决。这些算法基于增广路（augmenting path）的概念，通过不断寻找增广路并增加其上的流量来逼近最大流。

# 

# ### Python 代码示例

# 

# 下面是一个使用Ford-Fulkerson算法解决最大流问题的Python代码示例：

# 

# 

from collections import defaultdict, deque



class Graph:

    def __init__(self, vertices):

        self.V = vertices

        self.graph = defaultdict(list)



    def add_edge(self, u, v, w):

        self.graph[u].append((v, w))

        self.graph[v].append((u, 0))  # 反向边，初始容量为0



    def bfs(self, s, t, parent):

        visited = [False] * (self.V)

        queue = deque()

        queue.append(s)

        visited[s] = True

        parent[s] = None



        while queue:

            u = queue.popleft()



            for v, w in self.graph[u]:

                if visited[v] == False and w > 0:

                    queue.append(v)

                    parent[v] = u

                    visited[v] = True



        return visited[t]



    def ford_fulkerson(self, s, t):

        parent = [-1] * (self.V)

        max_flow = 0



        while self.bfs(s, t, parent):

            path_flow = float('inf')

            v = t



            # 找到增广路上的最小容量

            while v != s:

                u = parent[v]

                for i, (vertex, weight) in enumerate(self.graph[u]):

                    if vertex == v:

                        path_flow = min(path_flow, weight)

                        break

                v = parent[v]



            # 更新路径上的流量

            v = t

            while v != s:

                u = parent[v]

                for i, (vertex, weight) in enumerate(self.graph[u]):

                    if vertex == v:

                        self.graph[u][i][1] -= path_flow

                        self.graph[v][self.graph[v].index((u, 0))][1] += path_flow

                        break

                v = parent[v]



            max_flow += path_flow



        return max_flow



# 示例用法

g = Graph(4)

g.add_edge(0, 1, 16)

g.add_edge(0, 2, 13)

g.add_edge(1, 2, 10)

g.add_edge(2, 3, 12)

g.add_edge(1, 3, 4)



print("最大流为:", g.ford_fulkerson(0, 3))  # 输出应为20
